🎭 비트마스킹으로 부분집합 표현하기

원소 개수가 적을 때(보통 20개 이하), 각 원소의 포함 여부를 정수 하나의 비트로 표현해 모든 부분집합을 효율적으로 다루는 기법입니다.

1️⃣ 문제 접근

• 원소가 n개면, 0부터 2^n - 1까지의 정수가 각각 하나의 부분집합을 의미
• i번째 비트가 1이면 i번째 원소가 "포함됨"
• 반복문으로 모든 부분집합(2^n개)을 손쉽게 순회 가능

2️⃣ 풀이 코드 - 모든 부분집합 출력

function getAllSubsets(arr) {
  const n = arr.length;
  const result = [];

  for (let mask = 0; mask < (1 << n); mask++) {
    const subset = [];
    for (let i = 0; i < n; i++) {
      if (mask & (1 << i)) subset.push(arr[i]); // i번째 비트가 켜져 있으면 포함
    }
    result.push(subset);
  }

  return result;
}

getAllSubsets([1, 2, 3]);
// [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

• 1 << n은 원소 n개로 만들 수 있는 전체 부분집합의 개수(2^n)

✍️ 한 줄 정리

비트마스킹은 각 원소의 포함 여부를 정수의 비트 하나에 대응시켜, 원소 수가 적을 때 모든 부분집합을 배열 없이도 빠르게 다룰 수 있게 해준다.